#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;

// 线索二叉树节点结构定义
typedef struct ThreadNode
{
    ElemType data;
    struct ThreadNode *lchild;
    struct ThreadNode *rchild;
    int ltag;  // 0:指向子节点, 1:指向前驱线索
    int rtag;  // 0:指向子节点, 1:指向后继线索
}ThreadNode;

typedef ThreadNode *ThreadTree;

char str[] = "ABDH##I##EJ###CF##G##";
int idx = 0;
ThreadTree prev;  // 全局变量，记录前一个访问的节点

/**
 * 根据字符串递归创建二叉树
 */
void createThreadTree(ThreadTree *T)
{
    ElemType ch;
    ch = str[idx++];
    if(ch == '#')
    {
        *T = NULL;
    }
    else
    {
        *T = (ThreadTree)malloc(sizeof(ThreadNode));
        if(*T == NULL) {
            printf("内存分配失败\n");
            exit(1);
        }
        (*T)->data = ch;
        (*T)->ltag = 0;  // 显式初始化标签
        (*T)->rtag = 0;
        createThreadTree(&(*T)->lchild);
        createThreadTree(&(*T)->rchild);
    }
}

/**
 * 递归地为二叉树添加线索
 */
void threading(ThreadTree T)
{
    if(T == NULL)
    {
        return;
    }
    
    threading(T->lchild);  // 递归处理左子树
    
    // 处理当前节点的前驱线索
    if(T->lchild == NULL)
    {
        T->lchild = prev;
        T->ltag = 1;
    }
    
    // 处理前驱节点的后继线索（添加prev非空检查）
    if(prev != NULL && prev->rchild == NULL)
    {
        prev->rchild = T;
        prev->rtag = 1;
    }
    
    prev = T;  // 更新prev指针
    
    threading(T->rchild);  // 递归处理右子树
}

/**
 * 构建中序线索二叉树
 */
void inorderThreading(ThreadTree *head, ThreadTree T)
{
    *head = (ThreadTree)malloc(sizeof(ThreadNode));
    if(*head == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    (*head)->ltag = 0;
    (*head)->rtag = 1;
    (*head)->rchild = *head;
    
    if(T == NULL)
    {
        (*head)->lchild = *head;
    }
    else
    {
        (*head)->lchild = T;
        prev = *head;  // 初始化为头节点，避免prev为NULL
        threading(T);
        
        // 处理最后一个节点
        prev->rchild = *head;
        prev->rtag = 1;
        (*head)->rchild = prev;
    }
}

/**
 * 中序遍历线索二叉树
 */
void inOrder(ThreadTree T)
{
    ThreadTree curr;
    curr = T->lchild;
    
    while(curr != T)
    {
        // 找到最左节点
        while(curr->ltag == 0)
        {
            curr = curr->lchild;
        }
        
        printf("%c", curr->data);
        
        // 沿着后继线索访问
        while(curr->rtag == 1 && curr->rchild != T)
        {
            curr = curr->rchild;
            printf("%c", curr->data);
        }
        
        curr = curr->rchild;
    }
}

/**
 * 释放线索二叉树内存
 */
void freeThreadTree(ThreadTree T)
{
    if(T == NULL) return;
    
    if(T->ltag == 0)  // 如果是子节点指针，递归释放左子树
        freeThreadTree(T->lchild);
    
    if(T->rtag == 0)  // 如果是子节点指针，递归释放右子树
        freeThreadTree(T->rchild);
    
    free(T);
}

int main()
{
    ThreadTree head;
    ThreadTree T;
    
    createThreadTree(&T);
    inorderThreading(&head, T);
    printf("中序遍历结果：");
    inOrder(head);
    printf("\n");
    
    // 注意：这里不能直接释放head，因为线索二叉树形成了循环
    // 如果需要释放内存，需要特殊处理
    
    return 0;
}